Computing resource services and other services often provide responses to clients asynchronously. For instance, in response to a request from a client, a service provides a response to the request to another entity that can transfer the response to the client at a later time. However, it can be difficult to verify that the response obtained from the other entity originated from the server to which the request was sent or otherwise from a trusted entity. It may also be difficult to ensure that the response has not been tampered with from the time at which the response was generated to the time at which a client receives the response from the other entity.